/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       combat_obstacle_placer.cpp

	$Header: /game/combat_obstacle_placer.cpp $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "combat_obstacle_placer.h"

#include "battlefield.h"
#include "combat_context.h"
#include "combat_header_table.h"
#include "combat_header_table_cache.h"
#include "combat_object_model.h"
#include "combat_object_model_cache.h"
#include "combat_obstruction_finder.h"
#include "combat_start_position.h"
#include "combat_window.h"
#include "compound_object.h"
#include "compound_object_model.h"
#include "elements_of.h"
#include "enum_map.h"
#include "map_rect.h"
#include "obstacle_type.h"
#include "ptr_cache.h"
#include "random.h"
#include "resource_dir.h"
#include "stationary_combat_object.h"
#include "strip_resource_name.h"
#include "string_vector.h"
#include "table.h"
#include "table_ptr.h"
#include "terrain.h"

#include "profile.h"

namespace
{

	// ------------------------------------------------------------------
	// obstacle data
	// ------------------------------------------------------------------

	// ------------------------------------------------------------------
	// obstacle weighting data
	// ------------------------------------------------------------------
	enum t_frequency_type
	{
		k_frequency_unknown = -1,

		k_frequency_never,
		k_frequency_rare,
		k_frequency_seldom,
		k_frequency_common,
		k_frequency_usually,

		k_frequency_count
	};

#define DECLARE_KEYWORD( name ) k_frequency_##name, #name

	t_char_ptr_pair const k_frequency_keywords[] = 
	{
		{ DECLARE_KEYWORD( never ) },
		{ DECLARE_KEYWORD( rare ) },
		{ DECLARE_KEYWORD( seldom ) },
		{ DECLARE_KEYWORD( common ) },
		{ DECLARE_KEYWORD( usually ) },
	};

	t_enum_map<t_frequency_type> k_frequency_keyword_map( k_frequency_keywords,
							ELEMENTS_OF( k_frequency_keywords ),
							k_frequency_count );

	inline t_frequency_type get_frequency( std::string const& keyword )
	{
		return k_frequency_keyword_map[keyword];
	}
}

t_obstacle_placer_data::t_obstacle_placer_data()
{
	blocked = false;
	visited = false;
	can_be_blocked = true;
	obstacle_chance = 20;
	memset( adjacent, 0, sizeof( adjacent ));
	memset( overlap, 0, sizeof(overlap));
}

// ------------------------------------------------------------------
// get obstacle data
// ------------------------------------------------------------------
t_obstacle_data_array const& get_obstacle_data()
{
	static t_obstacle_data_array array;
	static bool					 initialized = false;

	if (!initialized)
	{
		declare_timer( timer, "Browse resource file" );

		t_combat_header_table_cache					cache;
		t_combat_header_table_ptr					data;
		
		cache = t_combat_header_table_cache(k_combat_header_table_name);
		data  = cache.get();
		
		data->fill_obstacle_array(array);
		initialized = true;
	}

	return array;
}

// ------------------------------------------------------------------
// read obstacle weighting
// ------------------------------------------------------------------
int const         k_type_column = 1;
static void read_terrain_weights( t_string_vector const& line, 
								  t_obstacle_weighting*  weighting,
								  int const*			 type_columns)
{
	static int const k_weights[k_frequency_count] = { 0, 5, 10, 20, 30 };
	t_terrain_type   terrain;
	int				 i;
	t_frequency_type frequency;

	terrain = get_terrain_type( line[k_type_column] );
	if (terrain == k_terrain_count)
		return;
	for (i = 0; i < k_obstacle_type_count; i++)
	{
		if (type_columns[i] < 0)
			continue;
		frequency = get_frequency( line[type_columns[i]] );
		if (frequency == k_frequency_unknown)
			continue;
		weighting[i].terrain[terrain] = k_weights[frequency];
	}
}

// ------------------------------------------------------------------
// read adjacent weighting
// ------------------------------------------------------------------
static void read_adjacent_weights( t_string_vector const& line, 
								   t_obstacle_weighting*  weighting,
								   int const*			 type_columns)
{
	static int const k_weights[k_frequency_count] = { -5000, 0, 10, 30, 100 };
	t_obstacle_type  type;
	int				 i;
	t_frequency_type frequency;

	type = get_obstacle_type( line[k_type_column] );
	if (type == k_obstacle_none)
		return;
	for (i = 0; i < k_obstacle_type_count; i++)
	{
		if (type_columns[i] < 0)
			continue;
		frequency = get_frequency( line[type_columns[i]] );
		if (frequency == k_frequency_unknown)
			continue;
		weighting[i].adjacent[type] = k_weights[frequency];
	}
}


// ------------------------------------------------------------------
// read overlap weighting
// ------------------------------------------------------------------
static void read_overlap_weights( t_string_vector const& line, 
								   t_obstacle_weighting*  weighting,
								   int const*			 type_columns)
{
	static int const k_weights[k_frequency_count] = { -5000, 0, 10, 30, 30 };
	t_obstacle_type  type;
	int				 i; 
	t_frequency_type frequency;

	type = get_obstacle_type( line[k_type_column] );
	if (type == k_obstacle_none)
		return;
	for (i = 0; i < k_obstacle_type_count; i++)
	{
		if (type_columns[i] < 0)
			continue;
		frequency = get_frequency( line[type_columns[i]] );
		if (frequency == k_frequency_unknown)
			continue;
		weighting[i].overlap[type] = k_weights[frequency];
	}
}

// ------------------------------------------------------------------
// read obstacle weighting
// ------------------------------------------------------------------
enum t_weight_category
{
	k_category_terrain,
	k_category_adjacent,
	k_category_overlap,

	k_category_count
};

static char const* k_category_keywords[k_category_count] =
{
	"terrain", "adjacent", "overlap"
};

static void read_weights( t_obstacle_weighting* weighting )
{
	// read table
	t_table_cache	  weight_table( "combat_obstacles" );
	t_table_ptr		  table = weight_table.get();
	t_table::iterator line = table->begin();
	std::string       name;
	int				  type_column[k_obstacle_type_count];
	int               i;
	t_obstacle_type   type;
	t_weight_category category;
	int const         k_category_column = 0;

	// read column headers
	for (i = 0; i < k_obstacle_type_count; i++)
		type_column[i] = -1;
	for (i = 0; i < line->size(); i++)
	{
		name = (*line)[i];
		type = get_obstacle_type( name );
		if (type == k_obstacle_none)
			continue;
		type_column[type] = i;
	}
	line++;
	category = k_category_terrain;

	while (line != table->end())
	{
		if (!(*line)[k_category_column].empty())
		{
			for (i = 0; i < k_category_count; i++)
			{
				if (stricmp( (*line)[k_category_column].c_str(), k_category_keywords[i] )
					== 0)
				{
					category = t_weight_category(i);
					break;
				}
			}
		}
		switch (category)
		{
			case k_category_terrain:
				read_terrain_weights( *line, weighting, type_column);
				break;
			case k_category_adjacent:
				read_adjacent_weights( *line, weighting, type_column );
				break;
			case k_category_overlap:
				read_overlap_weights( *line, weighting, type_column );
				break;
		}
		line++;
	}
}

// ------------------------------------------------------------------
// get obstacle weighting
// ------------------------------------------------------------------
t_obstacle_weighting const& get_weighting( t_obstacle_type type )
{
	static t_obstacle_weighting weighting[k_obstacle_type_count];
	static bool				    initialized = false;

	if (!initialized)
	{
		memset( weighting, 0, sizeof(weighting) );
		read_weights( weighting );
		initialized = true;
	}
	return weighting[type];
}


// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
t_combat_obstacle_placer::t_combat_obstacle_placer( t_battlefield& battlefield,
												    bool has_castle, int castle_row )
                        : m_battlefield( battlefield ),
						  m_data( battlefield.get_size(), 
						          k_battlefield_cell_height,
		                          k_battlefield_logical_view_size )
{
	m_has_castle = has_castle;
	m_castle_row = castle_row;
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::clear_rect( t_map_rect_2d const& rect )
{
	t_map_point_2d point;
	t_data*		   ptr;

	for (point.row = rect.top(); point.row < rect.bottom(); point.row++)
	{
		for (point.column = rect.left(); point.column < rect.right(); point.column++)
		{
			if (!m_data.is_valid( point ))
				continue;
			ptr = &m_data.get( point );
			ptr->can_be_blocked = false;

			t_battlefield_cell   const& cell = m_battlefield.get_cell( point );
			t_combat_object_list const& objects = cell.get_objects();
			t_combat_object_list::const_iterator	index = objects.begin();
			t_combat_object_list::const_iterator	last;
			t_stationary_combat_object const*		object;

			while (index != objects.end())
			{
				last = index;
				object = dynamic_cast<t_stationary_combat_object*>( last->get() );
				index++;
				if (object->blocks_movement() && object->get_obstacle_type() < k_obstacle_decorative_count)
				{
					m_battlefield.remove_object( *last );
				}
			}
		}
	}
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::clear_start_positions()
{
	int           side;
	t_map_rect_2d front_row;
	t_map_rect_2d back_row;
	t_map_rect_2d front_edge;
	t_map_rect_2d back_edge;
	int			  left_delta;
	int			  right_delta;

	for (side = 0; side < 2; side++)
	{
		if (m_has_castle && side == 1)
			continue;
		// clear front row
		front_row.top_left.row = k_combat_start_position[k_formation_loose][side][0].row - 3;
		front_row.top_left.column = k_combat_start_position[k_formation_loose][side][0].column - 3;
		front_row.bottom_right.row = k_combat_start_position[k_formation_loose][side][6].row + 4;
		front_row.bottom_right.column = k_combat_start_position[k_formation_loose][side][6].column + 4;
		clear_rect( front_row );

		// clear back row
		back_row.top_left.row = k_combat_start_position[k_formation_loose][side][1].row - 3;
		back_row.top_left.column = k_combat_start_position[k_formation_loose][side][1].column - 3;
		back_row.bottom_right.row = k_combat_start_position[k_formation_loose][side][5].row + 4;
		back_row.bottom_right.column = k_combat_start_position[k_formation_loose][side][5].column + 4;
		clear_rect( back_row );

		// clear intermediate rows
		if (back_row.top_left.row > front_row.top_left.row)
			std::swap( back_row, front_row );

		back_edge = back_row;
		back_edge.top_left.row = back_edge.bottom_right.row - 1;
		front_edge = front_row;
		front_edge.bottom_right.row = front_edge.top_left.row + 1;
		left_delta = sign_of( front_edge.top_left.column - back_edge.top_left.column );
		right_delta = sign_of( front_edge.bottom_right.column - back_edge.bottom_right.column );

		while (back_edge.top_left.row <= front_edge.top_left.row)
		{
			clear_rect( back_edge );
			back_edge.top_left.row++;
			back_edge.bottom_right.row++;
			back_edge.top_left.column += left_delta;
			back_edge.bottom_right.column += right_delta;
		}
		// clear last position of Square formation
		back_row.top_left = k_combat_start_position[k_formation_square][side][6];
		back_row.top_left -= t_map_point_2d( 3, 3 );
		back_row.bottom_right = back_row.top_left;
		back_row.bottom_right += t_map_point_2d( 7, 7 );
		clear_rect( back_row );
	}
	// clear area in front of gate
	if (m_has_castle)
	{
		t_map_rect_2d rect;

		rect.top_left.column = m_battlefield.get_gate_position().column;
		rect.top_left.row = m_castle_row;
		rect.bottom_right.column = rect.top_left.column + 7;
		rect.bottom_right.row = rect.top_left.row + 7;
		clear_rect( rect );
	}
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::cut_path( t_map_point_2d const& start_point, 
										 t_map_point_2d const& end_point,
										 int                   width )
{
	t_map_point_2d      point = start_point;
	t_map_point_2d      dest;
	t_map_point_2d      delta;
	t_map_point_2d      perpendicular;
	t_map_point_2d      mid_point;
	t_map_point_2d_list list;
	t_map_point_2d      origin_offset( (width - 1) / 2, (width - 1) / 2 );
	int					length;
	int					displacement;

	list.push_back( end_point );
	while (!list.empty() )
	{
		dest = list.back();
		delta = dest - point;
		if (abs(delta.column) < 2 && abs(delta.row) < 2)
		{
			t_map_rect_2d rect;
			
			rect.top_left = point - origin_offset;
			rect.bottom_right = rect.top_left + t_map_point_2d(width,width);
			clear_rect( rect );
			point = dest;
			list.pop_back();
			continue;
		}
		delta = delta / 2;
		length = (int)sqrt( (double)(delta.row * delta.row + delta.column * delta.column) );
		displacement = length / 2;
		if (displacement > 0)
			displacement = random( -displacement, displacement );
		if (displacement != 0)
		{
			perpendicular.row = -delta.column * displacement / length;
			perpendicular.column = delta.row * displacement / length;
			delta += perpendicular;
		}
		mid_point = point + delta;
		list.push_back( mid_point );
	}
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::cut_path( int size )
{
	t_map_point_2d start;
	t_map_point_2d stop;

	start.row = k_combat_start_position[k_formation_loose][0][0].row;
	start.column = random( k_combat_start_position[k_formation_loose][0][0].column,
		                   k_combat_start_position[k_formation_loose][0][6].column );
	stop.row = k_combat_start_position[k_formation_loose][1][0].row;
	if (m_has_castle)
		stop.row = m_castle_row + 4;
	stop.column = random( k_combat_start_position[k_formation_loose][1][0].column,
		                  k_combat_start_position[k_formation_loose][1][6].column );
	cut_path( start, stop, size );
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::cut_paths()
{
	// cut 3 paths, 1 of size 7, 2 of size 4.
	cut_path( 4 );
	cut_path( 4 );
	if (m_has_castle)
	{
		// cut a path to the gate.
		t_map_point_2d start;
		t_map_point_2d stop;

		start.row = k_combat_start_position[k_formation_loose][0][0].row;
		start.column = random( k_combat_start_position[k_formation_loose][0][0].column,
							   k_combat_start_position[k_formation_loose][0][6].column );
		stop.row = m_castle_row + 3;
		stop.column = m_battlefield.get_gate_position().column + 3;
		cut_path( start, stop, 7 );
	}
	else
	{
		cut_path( 7 );
	}
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::push_points( t_map_rect_2d const& object_rect, int size )
{
	t_map_rect_2d rect( object_rect.top() - size, object_rect.left() - size,
		                object_rect.bottom() + size, object_rect.right() + size );
	t_map_point_2d point;

	for (point.row = rect.top(); point.row < rect.bottom(); point.row++)
	{
		for (point.column = rect.left(); point.column < rect.right(); point.column++)
		{
			if (!m_data.is_valid( point ))
				continue;
			if (m_data.get( point ).visited)
				continue;
			m_open_points.push_back( point );
			m_data.get( point ).visited = true;
		}
	}
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::push_points( t_map_point_2d const& center, int size )
{
	t_map_rect_2d rect( center.row, center.column, center.row + 1, center.column + 1);

	push_points( rect, size );
}


// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
int t_combat_obstacle_placer::get_weight( t_combat_object_model_base const& obstacle,
										  t_map_point_2d const& center ) const
{
	t_map_point_2d				origin = center;
	t_map_point_2d				offset;
	t_map_point_2d				point;
	t_map_point_2d				footprint_size = obstacle.get_footprint_size();
	t_data const*				data;
	t_terrain_type			    terrain;
	int							result = 100;
	int						    weight = 5;
	t_obstacle_type				type = obstacle.get_type();
	t_obstacle_weighting const& weighting = get_weighting( type );

	origin.row -= (footprint_size.row - 1) / 2;
	origin.column -= (footprint_size.column - 1) / 2;
	for (offset.row = 0; offset.row < footprint_size.row; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size.column; offset.column++)
		{
			point = origin + offset;
			if (!m_data.is_valid( point ))
				return 0;
			data = &m_data.get( point );
			if (obstacle.blocks_movement() && !data->can_be_blocked)
				return 0;

			t_battlefield_cell& cell = m_battlefield.get_cell( point );
			
			terrain = cell.get_terrain_type();
			if (terrain == k_terrain_water_river)
				return 0;
			if (!cell.is_obstacle_allowed())
				return 0;
			if (m_battlefield.is_sea_battle())
				terrain = k_terrain_water;
			if (m_has_castle && point.row < m_castle_row)
				return 0;
			terrain = get_basic_terrain( terrain );
			if (weighting.terrain[terrain] <= 0)
				return 0;
			if (weighting.terrain[terrain] < result)
				result = weighting.terrain[terrain];
			weight += data->overlap[type] + data->adjacent[type];
			if (weight <= -5000)
				return 0;
		}
	}
	return result * weight;
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::place_obstacle( std::string const& name,
											   t_map_point_2d const& center )
{
	double						scale = m_battlefield.get_model_scale();
	t_combat_object_model_cache	cache = get_combat_object_model_cache( name, scale );
	t_compound_object_model_ptr model = cache.get();
	t_map_point_2d				origin = center;
	t_map_point_2d				footprint_size = model->get_footprint_size();
	t_map_point_2d				offset;
	t_map_point_2d				point;
	t_data*						data;
	t_obstacle_type				type = model->get_type();
	t_obstacle_weighting const& weighting = get_weighting( type );
	int							i;
	t_map_rect_2d               rect;

	origin.row -= (footprint_size.row - 1) / 2;
	origin.column -= (footprint_size.column - 1) / 2;
	m_battlefield.place_obstacle( cache, origin << k_battlefield_subcell_shift );
	rect.top_left = origin;
	rect.bottom_right = rect.top_left + footprint_size;
	push_points( rect, 2 );

	// mark overlap positions
	for (offset.row = 0; offset.row < footprint_size.row; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size.column; offset.column++)
		{
			point = origin + offset;
			if (!m_data.is_valid( point ))
				continue;
			data = &m_data.get( point );
			for (i = 0; i < k_obstacle_type_count; i++)
				data->overlap[i] += weighting.overlap[i];
		}
	}

	// mark adjacent positions
	int zone_width = 3;

	for (offset.row = -zone_width; offset.row < footprint_size.row + zone_width; offset.row++)
	{
		for (offset.column = -zone_width; offset.column < footprint_size.column + zone_width; offset.column++)
		{
			point = origin + offset;
			if (!m_data.is_valid( point ))
				continue;
			data = &m_data.get( point );
			for (i = 0; i < k_obstacle_type_count; i++)
				data->adjacent[i] += weighting.adjacent[i];
		}
	}

	// mark adjacent positions as higher chances
	zone_width = (footprint_size.column + footprint_size.row - 2) / 3;
	if (zone_width <= 0)
		return;
	for (offset.row = -zone_width; offset.row < footprint_size.row + zone_width; offset.row++)
	{
		for (offset.column = -zone_width; 
		     offset.column < footprint_size.column + zone_width; offset.column++)
		{
			point = origin + offset;
			if (!m_data.is_valid( point ))
				continue;
			data = &m_data.get( point );
			for (i = 0; i < k_obstacle_type_count; i++)
				data->obstacle_chance = 200;
		}
	}
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::examine( t_map_point_2d const& center )
{
	t_data* data = &m_data.get( center );

	if (random(1000) >= data->obstacle_chance || !data->can_be_blocked)
	{
		push_points( center, 1 );
		return;
	}

	t_obstacle_data_array const& obstacle_data = get_obstacle_data();
	int							 i;
	t_obstacle_weight_list		 weight_list;
	t_obstacle_weight			 weight;
	int							 total = 0;
	int							 type_count[k_obstacle_type_count];

	memset( type_count, 0, sizeof( type_count ));
	for (i = 0; i < (int)obstacle_data.size(); i++)
	{
		weight.obstacle = &obstacle_data[i];
		weight.weight = get_weight( weight.obstacle->obstacle, center );
		if (weight.weight <= 0)
			continue;
		++type_count[weight.obstacle->obstacle.get_type()];
		weight_list.push_back( weight );
	}

	t_obstacle_weight_list::iterator index = weight_list.begin();
	t_obstacle_weight_list::iterator end = weight_list.end();
	t_obstacle_weight*				 weight_ptr;
	int								 max_count = 0;

	for (i = 0; i < k_obstacle_type_count; ++i)
	{
		if (type_count[i] > max_count)
			max_count = type_count[i];
	}

	for (; index != end; ++index)
	{
		weight_ptr = &(*index);
		weight_ptr->weight = weight_ptr->weight * max_count
			                 / type_count[weight_ptr->obstacle->obstacle.get_type()];
		if (weight_ptr->weight < 1)
			weight_ptr->weight = 1;
		total += weight_ptr->weight;
	}

	if (total == 0)
	{
		push_points( center, 1 );
		return;
	}

	int						         choice = random( total );

	for (index = weight_list.begin(); index != end; index++)
	{
		weight = *index;
		choice -= weight.weight;
		if (choice <= 0)
			break;
	}
	place_obstacle( weight.obstacle->name, center );
}

// --------------------------------------------------------------------
// object to place combat obstacles
// --------------------------------------------------------------------
void t_combat_obstacle_placer::execute()
{
	t_map_point_2d point;

	declare_timer( timer, "Place obstacles" );
	clear_start_positions();

	t_combat_window* window = m_battlefield.get_combat_window();
	t_combat_context* context = window->get_context();
	t_adv_map_point		location = context->get_location();

	if (!location.on_bridge)
		cut_paths();

	point.row = m_data.get_size() - 1;
	point.column = m_data.get_row_start( point.row );
	m_open_points.push_back( point );
	m_data.get( point ).visited = true;
	while (!m_open_points.empty())
	{
		point = m_open_points.front();
		m_open_points.pop_front();
		examine( point );
	}

	if (location.on_bridge)
		return;

	t_combat_obstruction_finder finder( m_battlefield, m_has_castle );
	t_map_point_2d              start_point;
	t_map_point_2d              offset(3,3);
	t_map_point_2d				last_point(-1,-1);

	while (finder.find_obstruction( point ))
	{
		t_combat_path	path;
		int				i;

		assert( point != last_point );
		if (point == last_point)
			break;
		last_point = point;
		finder.get_path( point, path );
		if (path.empty())
			return;
		for (i = 0; i < (int)path.size(); ++i)
		{
			t_map_rect_2d rect;
			
			rect.top_left = path[i];
			rect.bottom_right = rect.top_left + t_map_point_2d(7,7);
			clear_rect( rect );
		}
		finder.seed( path.back() );
	}
}

